class Solution {
public:
    void sortColors(vector<int>& nums)
    {
        _sort(nums, 0, nums.size() - 1);
    }

    void _sort(vector<int>& nums, int left, int right)
    {
        if (left >= right) return;

        int key = right;
        int cur = left, pre = cur - 1;

        while (cur < right)
        {
            while (nums[cur] < nums[key] && ++pre < cur)
            {
                swap(nums[cur], nums[pre]);
            }
            cur++;
        }
        swap(nums[++pre], nums[key]);
        key = pre;

        _sort(nums, left, key - 1);
        _sort(nums, key + 1, right);
    }
};